1. Field of the Invention
The present invention relates generally to novel architecture and circuitry for implementing a new two dimensional fast fourier transform algorithm, and more particularly pertains to a novel pipelined and parallel architecture for implementing a new two dimensional fast fourier transform algorithm which is developed herein.
2. Discussion of the Prior Art
Two dimensional Fast Fourier Transform (FFT) has been widely applied in the areas of image enhancement, image coding, image compression and restoration, radar, and tomography. Two major problems have existed in the implementation of a two dimensional FFT either in software or hardware. One is the problem of data storage, since a practically useful two dimensional FFT normally requires a very large core memory in the execution of the algorithm. For example, a 512.times.512 FFT for radar applications would normally require 512K bytes core memory which is beyond the capacity of most systems. In many applications the matrix is stored on a mass storage device, e.g. a disk or a tape, where the smallest record that can be easily accessed is an entire row or column.
Avoidance of heavy traffic between the main memory and a second memory is a first crucial problem to the implementation of an efficient two dimensional FFT. Another problem is in the matrix transpose. In the literature, most algorithms and/or their implementations require the transpose of a matrix either by Single Instruction Multiple Data (SIMD) or by conventional machine. The efficient storage of data in the secondary storage device such that it can avoid the matrix transpose or minimize the traffic between the main memory and the secondary memory is also a crucial problem.
Two kinds of two dimensional FFT algorithms have been proposed in the prior art literature. In one, a two dimensional transform is accomplished by executing one dimensional FFT row-column wisely (column-row wisely). The other is a vector algorithm. Implementing a two dimensional FFT in a Von Neumann machine using either a row-column-wise algorithm or a vector algorithm normally causes a serious traffic problem between the main and secondary memories and therefore produces extremely poor performance. On the other hand, implementing a two dimensional FFT in a SIMD or Multiple Instruction, Multiple Data (MIMD) environment using row-column-wise algorithm still faces the serious problem of the matrix transpose and does not have high processor utilization.